#include <bits/stdc++.h>
using namespace std;

/*
3186. 施咒的最大总伤害
已解答
中等
相关标签
premium lock icon
相关企业
提示
一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用 一次 。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。

 

示例 1：

输入：power = [1,1,3,4]

输出：6

解释：

可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。

示例 2：

输入：power = [7,1,6,6]

输出：13

解释：

可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。

 

提示：

1 <= power.length <= 105
1 <= power[i] <= 109
*/

// 法一
class Solution {
public:
    using ll = long long;
    long long maximumTotalDamage(vector<int>& power) {
        // 统计每个伤害值的总贡献（伤害值 × 出现次数，相同伤害值要么全选要么全不选）
        unordered_map<int, ll> sum_map;
        for (int p : power) sum_map[p] += p;
        // 提取不同的伤害值 sort DESC 处理相邻禁止关系
        vector<int> sorted_powers;
        for (const auto& pair : sum_map)    sorted_powers.push_back(pair.first);
        sort(sorted_powers.begin(), sorted_powers.end());

        int m = sorted_powers.size();
        // edge condition
        if (m == 0) return 0;
        if (m == 1) return sum_map[sorted_powers[0]];

        // 常规 使用dp  dp[i] = 处理到第i个不同伤害值时的最大总伤害
        vector<ll> dp(m);
        // init 1 max
        dp[0] = sum_map[sorted_powers[0]];
        // 初始化第二个伤害值的最大伤害（判断与第一个是否冲突）
        int p_first = sorted_powers[0];
        int p_second = sorted_powers[1];
        dp[1] = (p_second - p_first > 2) ? (dp[0] + sum_map[p_second]) : max(dp[0], sum_map[p_second]);

        // 后续 foreah 逐个判断
        for (int i = 2; i < m; i++) {
            int cur_p = sorted_powers[i];
            ll cur_val = sum_map[cur_p];
            int pre1 = sorted_powers[i - 1];
            int pre2 = sorted_powers[i - 2];
            
            if (cur_p - pre1 > 2) dp[i] = dp[i - 1] + cur_val;  // 情况1：与前一个不冲突，直接累加前一个的最大伤害
            else {
                if (cur_p - pre2 > 2) dp[i] = max(dp[i - 1], dp[i - 2] + cur_val);  // 情况2：与前一个冲突，但与前两个不冲突，累加前两个的最大伤害
                else {
                    // 情况3：与前两个也冲突，选“前三个最大伤害+当前值”或“前一个最大伤害”的较大者
                    ll pre3 = (i >= 3) ? dp[i - 3] : 0;
                    dp[i] = max(dp[i - 1], pre3 + cur_val);
                }
            }
        }
        return dp.back();       // 最终最大伤害和为最后一个状态的值
    }
};

// 法二
class Solution {
public: 
    /**
     * 思路：先去重统计伤害值出现次数，再通过动态规划找最大伤害和（避免冲突：差值1/2的伤害值）
     * @param power 咒语伤害值数组
     * @return 最大总伤害
     */
    long long maximumTotalDamage(std::vector<int> &power) {
        int size = power.size();
        if (size == 1) { // 边界：仅1个咒语，直接返回其伤害
            return power[0];
        }

        std::sort(power.begin(), power.end()); // 排序：便于去重和冲突判断
        int sum = 1; // 统计当前伤害值的出现次数
        std::vector<int>& opt_power = power; // 复用power数组存储去重后的伤害值
        int opt_index = 0; // 去重后伤害值的索引
        std::vector<int> opt_power_count; // 存储每个去重伤害值的出现次数
        opt_power_count.reserve(size >> 1); // 预分配空间优化性能

        // 1. 去重并统计每个伤害值的出现次数
        for (int i = 1; i < size; i++) {
            if (power[i] == power[i - 1]) { // 相同伤害值，累加次数
                sum += 1;
            } else { // 不同伤害值，记录前一个的次数并更新
                opt_power[++opt_index] = power[i];
                opt_power_count.push_back(sum);
                sum = 1;
            }
        }
        opt_power_count.push_back(sum); // 补充最后一个伤害值的次数

        int opt_size = opt_power_count.size(); // 去重后的伤害值种类数
        // 动态数组类型改为 long long*，与 curr_total 类型一致
        long long *max = new long long[opt_size]; 

        // 2. DP初始化：第一个去重伤害值的总贡献（伤害值 × 次数）
        max[0] = (long long)opt_power[0] * opt_power_count[0];

        // 3. DP转移：遍历每个去重伤害值，计算最大总伤害
        for (auto i = 1; i < opt_size; i++) {
            // 初始值：仅选当前伤害值的总贡献（long long 类型）
            long long curr_total = (long long)opt_power[i] * opt_power_count[i];
            // 向前找第一个不冲突的伤害值（差值>2），累加其最大伤害
            for (int j = i - 1; j >= 0; j--) {
                if (opt_power[i] - opt_power[j] > 2) { // 无冲突，可累加
                    curr_total = max[j] + curr_total;
                    break; // 找到最近的不冲突前驱即可
                }
            }
            // 两个参数均为 long long 类型，std::max 可正常匹配
            max[i] = std::max(max[i - 1], curr_total);
        }

        long long ans = max[opt_size - 1]; // 结果类型统一为 long long
        delete[] max; // 释放动态内存，避免泄漏

        return ans;
    }
};